package 剑指offer;

public class p47礼物的最大价值 {
    //由于 dp[i][j]只与 dp[i-1][j]和dp[i−1][j]， grid[i][j]grid[i][j] 有关系，
    //因此可以将原矩阵grid用作 dp矩阵，即直接在 grid上修改即可。
    //应用此方法可省去 dp矩阵使用的额外空间，因此空间复杂度从 O(MN)降至 O(1) 。
    public int maxValue1(int[][] grid) {
        int m=grid.length;    // m行
        int n=grid[0].length; // n列

        for (int i = 0; i <m; i++) {
            for (int j = 0; j <n; j++) {
                if (i==0 && j==0) {
                    continue;
                }else if (i==0) {
                    //第一行的元素，只能由左边元素到达
                    grid[i][j] = grid[i][j]+grid[i][i-1];
                }else if (j==0) {
                    //第一列元素，只能由上面元素到达
                    grid[i][j] = grid[i][j]+grid[i-1][j];
                }else {
                    //可能由左边元素到达 或者 由上面元素到达
                    grid[i][j] = grid[i][j]+Math.max(grid[i-1][j],grid[i][j-1]);
                }
            }
        }
        return grid[m-1][n-1];
    }


    public int maxValue(int[][] grid) {
        //开辟 m+1行 n+1列的 dp数组，使代码更简洁
        int m=grid.length;
        int n=grid[0].length;

        int[][] dp=new int[m+1][n+1];

        for (int i = 1; i <=m; i++) {
            for (int j = 1; j <=n; j++) {
                dp[i][j]=grid[i-1][j-1] + Math.max(dp[i][j-1],dp[i-1][j]);
            }
        }
        return dp[m][n];

    }
}
